package org.basis.algorithm.promote;

import java.util.ArrayList;
import java.util.List;

/**
 * 查找所有子集
 * 相似题型：力扣的2044题：https://leetcode-cn.com/problems/count-number-of-maximum-bitwise-or-subsets/submissions/
 *
 * @author Mr_wenpan@163.com 2022/03/16 15:46
 */
public class FindAllSubset {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        List<List<Integer>> lists = find(arr);
        System.out.println(lists);

        List<List<Integer>> subset = findSubset(arr);
        System.out.println(subset);
    }

    public static List<List<Integer>> findSubset(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }
        List<List<Integer>> resultList = new ArrayList<>();
        process(arr, 0, new ArrayList<>(), resultList);
        return resultList;
    }

    /**
     * 迭代法求所有子数组
     */
    public static List<List<Integer>> find(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }
        List<List<Integer>> lists = new ArrayList<>();

        // 对于每一个位置都求包含他自己在内的所有子数组
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                // 逐个求子数组
                List<Integer> list = new ArrayList<>();
                for (int k = i; k <= j; k++) {
                    list.add(arr[k]);
                }
                lists.add(list);
            }
        }

        return lists;
    }

    /**
     * 递归 + 回溯解法
     */
    private static void process(int[] arr, int index, List<Integer> supList, List<List<Integer>> resultList) {
        // base case
        if (index >= arr.length) {
            resultList.add(supList);
            return;
        }
        // 每一个位置都可以选择要或者不要
        // 将上一层调用传过来的集合拷贝一份
        List<Integer> copy = copy(supList);
        copy.add(arr[index]);
        // 要当前位置
        process(arr, index + 1, copy, resultList);
        // 不要当前位置
        process(arr, index + 1, supList, resultList);
    }

    private static List<Integer> copy(List<Integer> res) {
        return new ArrayList<>(res);
    }
}
